//
// Created by Jisam on 2024/7/28 17:23.
// solve G - Last Major City
#include <bits/stdc++.h>

#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

using namespace std;

constexpr i64 inf = 1E18;
/**
 * @brief 解决最短路径问题的函数
 *
 * 本函数通过动态规划和并查集的方法解决了一类特殊的最短路径问题。
 * 具体而言，它计算了一个有n个顶点和m条边的图中，k个指定顶点到其他所有顶点的最短路径。
 * 边的权重可能是负值。
 */
void solve() {
    /* 输入顶点数n，边数m，和指定的k个顶点 */
    int n,m,k;
    cin >> n >> m >>k;

    /* 构建邻接表adj，用于存储图的结构 */
    vector<vector<PII>> adj(n);
    /* 输入m条边，并以无向图形式存储在邻接表中 */
    for(int i = 0 ; i < m ; i ++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        a --;
        b --;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    /* 初始化动态规划数组dp，用于存储从指定顶点集合到每个顶点的最短路径 */
    vector dp(1 <<( k - 1 ) ,vector<i64>(n,inf));
    /* 初始化dp数组，设置从单个指定顶点到其他顶点的最短距离为0 */
    for(int i = 0 ; i  < k  - 1; i ++)
    {
        dp[1 << i][i] = 0;
    }
    /* 动态规划过程，更新dp数组以包含所有指定顶点集合到每个顶点的最短路径 */
    for(int s = 0; s < (1 << (k - 1)); s ++)
    {
        /* 使用优先队列来维护当前状态下最短路径的信息 */
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<>> pq;
        /* 通过位运算更新dp数组，以考虑所有可能的指定顶点集合 */
        for(int t = s; t != 0 ;t = ( t - 1)& s){
            for(int i = 0 ; i < n ;i ++)
            {
                dp[s][i] = min(dp[s][i],dp[t][i] + dp[s ^ t][i]);
            }
        }
        /* 将当前状态下所有可能的最短路径加入优先队列 */
        for(int i = 0 ;i < n; i ++)
        {
            if(dp[s][i] != inf){
                pq.emplace(dp[s][i],i);
            }
        }
        /* 通过优先队列更新dp数组，考虑边的权重影响 */
        while(!pq.empty()){
            auto [d,x] =pq.top();
            pq.pop();

            if(d != dp[s][x]){
                continue;
            }

            /* 更新通过顶点x的最短路径，并将新路径加入优先队列 */
            for(auto [y,w] : adj[x]){
                if(dp[s][y] > dp[s][x] + w)
                {
                    dp[s][y] = dp[s][x] + w;
                    pq.emplace(dp[s][y],y);
                }
            }
        }
    }
    /* 输出每个顶点到所有指定顶点的最短路径长度 */
    for (int i = k - 1; i < n; i++) {
        cout << dp[(1 << (k - 1)) - 1][i] << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) solve();
//    cout << "\n"[];
    return 0;
}